package org.example.everyday;

import com.sun.org.apache.xpath.internal.operations.Mod;

import java.util.Arrays;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/6/10 17:59
 */
public class Lc730 {
    public static void main(String[] args) {
        Lc730 lc730 = new Lc730();

        String s = "bccb";
        int res = lc730.countPalindromicSubsequences(s);
        System.out.println(res);

    }


    /**
     * 方法描述: 三维的数组动态规划
     *
     * @param s .
     * @return int
     * @author 安路路
     * @date 2022/6/13  10:47
     */
    public int countPalindromicSubsequences(String s) {
        final int MOD  = 1000000007;
        int n = s.length();
        int[][][] dp = new int[4][n][n];
        for (int i = 0; i < n; i++) {
            dp[s.charAt(i) - 'a'][i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i +len <= n; i++) {
               int j = i + len  - 1;
               for (char c = 'a'; c <= 'd'; c++){
                   int k = c - 'a';
                   if(s.charAt(i) == c && s.charAt(j)==c){
                       dp[k][i][j] = (2 + (dp[0][i+1][j-1] + dp[1][i+1][j-1]) % MOD + (dp[2][i+1][j-1]) % MOD) % MOD;
                   }else if(s.charAt(i) == c){
                       dp[k][i][j] = dp[k][i][j - 1];
                   }else if(s.charAt(j) == c){
                       dp[k][i][j] = dp[k][i + 1][j];
                   }else{
                       dp[k][i][j] = dp[k][i + 1][j - 1];
                   }
               }
            }
        }

        int res = 0;
        for (int i = 0; i < 4; i++) {
            res = (res + dp[i][0][n - 1]) % MOD;
        }

        return  res;

    }


}
